package com.maduar.demo.algo.interview;

import java.util.List;

/**
 * Description:
 *
 * @author maduar maduar@163.com
 * @date 2021-04-03 23:02
 */
public class LongestCommonSubsequence {

    public static int longestCommonSubsequence(String text1, String text2) {
        int l1 = text1.length();
        int l2 = text2.length();
        if (l1 == 0) {
            return 0;
        }

        int[][] dp = new int[l1 + 1][l2 + 1];
        for (int i = 1; i <= l1; i++) {
            for (int j = 1; j <= l2; j++) {
                if (text1.charAt(i - 1) == text2.charAt(j - 1)) {
                    dp[i][j] = dp[i - 1][j - 1] + 1;
                } else {
                    dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);
                }
            }
        }

        return dp[l1][l2];
    }

    public static int longestCommonSubsequence2(String text1, String text2) {
        int l1 = text1.length();
        int l2 = text2.length();
        if (l1 == 0) {
            return 0;
        }

        char[] c1 = text1.toCharArray();
        char[] c2 = text2.toCharArray();

        int[][] dp = new int[l1 + 1][l2 + 1];
        for (int i = 1; i <= l1; i++) {
            for (int j = 1; j <= l2; j++) {
                if (c1[i - 1] == c2[j - 1]) {
                    dp[i][j] = dp[i - 1][j - 1] + 1;
                } else {
                    dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);
                }
            }
        }

        return dp[l1][l2];
    }

    public static int bag(int[] wArr, int[] vArr,  int v) {
        int n = wArr.length;

        int[][] dp = new int[n + 1][v + 1];

        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= v; j++) {
                // 包装不进,最后一件商品无法装进背包
                if (wArr[i - 1] > j) {
                    dp[i][j] = dp[i - 1][j];
                } else {
                    // j - wArr[i-1] 去掉最后一件商品的重量
                    // vArr[i - 1] 最后一件商品的价格
                    dp[i][j] = Math.max(dp[i - 1][j], dp[i - 1][j - wArr[i-1]] + vArr[i - 1]);
                }
            }
        }

        return dp[n][v];
    }

    public static int level(int n) {
        if (n == 1) {
            return 1;
        }
        if (n == 2) {
            return 2;
        }

        int[] arr = new int[n + 1];
        arr[1] = 1;
        arr[2] = 2;

        for (int i = 3; i <= n; i++) {
            arr[i] = arr[i - 1] + arr[i - 2];
        }

        return arr[n];
    }

    /**
     * 1. 接口名称: 三角形最短路径
     * 2. 接口文档编号:
     * 3. 接口详细说明: dp[i][j] = arr[i][j] + min(dp[i+1][j] + dp[i+1][j+1]);
     * @param
     * @return
     * @Author: danny.pang
     * @Date: 2021-04-04 22:03:05
     */
    public static int triangle(List<List<Integer>> triangle) {
        int size = triangle.size();
        if (size == 1) {
            return triangle.get(0).get(0);
        }

        int[][] dp = new int[size + 1][size + 1];
        for (int i = size - 1; i >= 0; i--) {
            for (int j = 0; j <= i; j++) {
                dp[i][j] = triangle.get(i).get(j) + Math.min(dp[i + 1][j], dp[i + 1][j + 1]);
            }
        }

        return dp[0][0];
    }

    public static int triangle2(List<List<Integer>> triangle) {
        int size = triangle.size();
        int[] dp = new int[size + 1];
        for (int i = size - 1; i >= 0; i--) {
            for (int j = 0; j <= i; j++) {
                dp[j] = Math.min(dp[j], dp[j + 1]) + triangle.get(i).get(j);
            }
        }

        return dp[0];
    }

    public static int minPathSum(int[][] grid) {
        for (int i = 0; i < grid.length; i++) {
            for (int j = 0; j < grid[0].length; j++) {
                if (i == 0 && j == 0) {
                    continue;
                } else if (i == 0) {
                    grid[i][j] = grid[i][j - 1] + grid[i][j];
                } else if (j == 0) {
                    grid[i][j] = grid[i - 1][j] + grid[i][j];
                } else {
                    grid[i][j] = Math.min(grid[i - 1][j], grid[i][j - 1]) + grid[i][j];
                }
            }
        }
        return grid[grid.length - 1][grid[0].length - 1];
    }
}
